/**
gcc shellsort.c && ./a.out
gcc shellsort.c -DDEBUG && a
gcc shellsort.c -DDEBUG && ./a.out
  */
#include<stdio.h>
#include<ctype.h>
#include<string.h>
#include"shellsort.h"
//#define DEBUG

void shell_sort(struct wordnode *x, int n)
{
	int h, j, k;
	struct wordnode tmp;

	for (h=n/2; h>0; h=h/2) /*控制增量*/
	{
		for (j=h; j<n; j++) /*这个实际上就是上面的直接插入排序*/
		{
			sprintf(tmp.word,"%s",x[j].word);
			tmp.counter= x[j].counter;
			for (k=j-h; (k>=0 /*&& strcmp(tmp.word,x[k].word)<0*/); k-=h)
			{
				/**
				 * tolowercase; ignore the case;
				 */
				char s1[strlen(tmp.word)+1];
				sprintf(s1,"%s",tmp.word);
				int p=0;
				while(p<strlen(s1)){
					s1[p]=tolower(s1[p]);
					p++;
				}
				char s2[strlen(x[k].word)+1];
				sprintf(s2,"%s",x[k].word);
				p=0;
				while(p<strlen(s2)){
					s2[p]=tolower(s2[p]);
					p++;
				}       
				if(strcmp(s1,s2)>=0)break;

				sprintf((x[k+h]).word ,"%s", s2/*(x[k]).word*/);
				(x[k+h]).counter= (x[k]).counter;
			}
			sprintf(x[k+h].word,"%s", tmp.word);
			x[k+h].counter= tmp.counter;
		}
	}
}


void bubble(char**a,int n) /*定义两个参数：数组首地址与数组大小*/
{
	int i,j;
	char *temp;
	for(i=0;i<n-1;i++)
		for(j=i+1;j<n;j++) /*注意循环的上下限*/
			if(strcmp((char*)(a[i]),(char*)(a[j]))>0) {
				temp=(char*)(a[i]);
				a[i]=a[j];
				a[j]=temp;
			}
}
#ifdef DEBUG
int main()
{
	char * a[4444];
	char* a1;
	char* a2;
	char* a3;
	char* a4;
	char aa[100]="za";
	char aa2[100]="cd";
	char aa3[100]="fi";
	char aa4[100]="a";

	printf("%d\n",strcmp("ai","ab"));
	a1=aa;
	a2=aa2;
	a3=aa3;
	a4=aa4;
	a[0]=a1;
	a[1]=a2;
	a[2]=a3;
	a[3]=a4;
	printf("a1:%s,a2:%s,a3:%s,a4:%s\n",a[0],a[1],a[2],a[3]);
	bubble(a,4);
	printf("\na1:%s,a2:%s,a3:%s,a4:%s",a[0],a[1],a[2],a[3]);
	return 0;

}
#endif
/*
*/
